public class MyOneLinkList {
    static class Node {
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node phead;
    //尾插
    public void addLast(int date){
        Node node1 = new Node(date);
        if(phead == null){
            phead = node1;
            return;
        }

        Node cur = phead;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node1;
    }
    //打印
    public void Display(){
        Node cur = phead;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
    //创建链表
    public void Creatlist(){
        Node node1 = new Node(12);
        Node node2 = new Node(34);
        Node node3 = new Node(56);
        Node node4 = new Node(78);

        phead = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;


    }
    //头插
    public void addFrist(int date){
        Node node1 = new Node(date);
       node1.next = phead;
        phead = node1;

    }
    //获取链表长度
    public int getsize(){
        Node cur = phead;
        int count = 0;
        while (cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
    //随即插
    public void add(int pos,int date){
        if(pos < 0 || pos > getsize()){
            System.out.println("添加越界");
            return;
        }
        if(pos == 0){
            addFrist(date);
            return;
        }
        if (pos == getsize()){
            addLast(date);
            return;
        }
        Node node1 = new Node(date);
        if(phead == null){
            phead = node1;
            return;
        }
        Node cur = phead;
        for (int i = 0; i < pos - 1; i++) {
            cur = cur.next;
        }
        node1.next = cur.next;
        cur.next = node1;
    }
    //头删
    public void removeFrist(){
        if(phead == null){
            System.out.println("链表为空");
            return;
        }
        phead = phead.next;
    }
//尾删
    public void removeLast(){
        if(phead == null){
            System.out.println("链表为空");
            return;
        }
        if(phead.next == null){
            removeFrist();
            return;
        }
        Node cur = phead;
        while (cur.next.next!= null){
            cur = cur.next;
        }
        cur.next = null;
    }
//随机删
    public void removePos(int pos){
        if(pos < 0 || pos >= getsize()){
            System.out.println("位置越界");
            return;
        }
        if(pos == 0){
            removeFrist();
            return;
        }
        if (pos == getsize() - 1){
            removeLast();
            return;
        }
        Node cur = phead;
        for (int i = 0; i < pos - 1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
    //删除指定数据val
    public void removeVal(int val){
        if(phead == null){
            System.out.println("链表为空");
            return;
        }
        Node cur = phead;
        if(phead.val == val){
            removeFrist();
            return;
        }
        while (cur.next.val != val && cur.next != null){
            cur = cur.next;
        }
        if(cur.next == null){
            System.out.println("没找到");
        }else if(cur.next.val == val){
            cur.next = cur.next.next;
        }
    }
//删除所有val
    public void removeAll(int val){
        if(phead == null){
            System.out.println("链表为空");
            return;
        }
        Node cur = phead;
        while (cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }
        }
        if(phead.val == val){
            removeFrist();
        }
    }
    //清空链表
    public void ClearList(){
        phead = null;
    }
    //修改val
    public void setlist(int pos,int val){
        if(pos < 0 || pos >= getsize()){
            System.out.println("位置越界");
            return;
        }
        Node cur = phead;
        //找到pos位置
        for (int i = 0; i < pos; i++) {
            cur = cur.next;
        }
        cur.val = val;
    }
    //反转链表
    public void reversaList(){
        if(phead == null){
            System.out.println("链表为空");
            return;
        }
        if(phead.next == null){
            return;
        }
        Node cur = phead.next;
        phead.next = null;

        while(cur != null){
            //记录下来当前要反转的节点的下一个节点
            Node curNext = cur.next;
            cur.next = phead;
            phead = cur;
            cur = curNext;
        }

    }
    //交换
    public void Swap(Node node1,Node node2){
        int t = node1.val;
        node1.val = node2.val;
        node2.val = t;
    }
    //合并两个排序的链表
    public Node combineList(Node head1,Node head2){
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        Node phead;
        Node cur;
        if(head1.val < head2.val){
             phead = head1;
             cur = phead;
            head1 = head1.next;
        }else{
             phead = head2;
             cur = phead;
            head2 = head2.next;
        }
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                cur = cur.next;
                head1 = head1.next;

            }else{
                cur.next = head2;
                cur = cur.next;
                head2 = head2.next;
            }

        }
        if(head1 == null){
            cur.next = head2;
        }else{
            cur.next = head1;
        }
        return phead;
    }
    //链表分割
    public Node divisionList(int val,Node pHead){
        if(pHead == null){
            return pHead;
        }
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = pHead;
        while (cur != null){
           if(cur.val < val){
               //第一次
               if(bs == null){
                   bs = cur;
                   be = cur;
               }else{
                   be.next = cur;
                   be = be.next;
               }
           }else{
               //第一次插入
               if(as == null){
                   as = cur;
                   ae = cur;
               }else {
                   ae.next = cur;
                   ae = ae.next;
               }
           }
           cur = cur.next;
        }
        if(bs == null){
            return as;
        }
        be.next = as;
        //防止死循环
        ae.next = null;
        return be;
    }
    //求两个链表相交交点
    public Node getIntersectionNode(Node headA, Node headB) {
        int lenA = 0;//A的长
        int lenB = 0;//B的长
        Node cur1 = headA;
        while(cur1!=null){
            cur1 = cur1.next;
            lenA++;
        }
        Node cur2 = headB;
        while(cur2 != null){
            cur2 = cur2.next;
            lenB++;
        }
        if(lenA - lenB > 0){
            for(int i = 0;i < lenA - lenB;++i){
                headA = headA.next;
            }
        } else{
            for(int i=0;i< lenB - lenA;++i){
                headB = headB.next;
            }
        }
        while(headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
    public Node deleteDuplication(Node pHead){
        if(pHead == null){
            return pHead;
        }
        Node cur = pHead;
        Node Newh = new Node(-1);
        Node th = Newh;
        //遍历每一个节点
        while(cur != null){
            if(cur != null && cur.val == cur.next.val){
                //一直让cur走到不重复的节点，然后把这个节点加到不重复的链表中
                while (cur != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                //这里走完cur会停在重复数据的最后一个节点，要让cur再向前走一个
                cur = cur.next;
                //将不重复节点放到新链表
            }else {
                th.next = cur;
                th = th.next;
                cur = cur.next;
            }
        }
        th.next = null;
        return Newh;
    }
}

